package hot100;

import static hot100.ListNode.generateList;

import java.util.List;

public class Solution143 {
    public void reorderList(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
            fast = fast.next;
        }
        ListNode mid = reverse(slow.next);
        slow.next = null;
        ListNode p1 = head;
        ListNode p2 = mid;
        while (p1 != null && p2 != null) {
            ListNode tmp = p1.next;
            p1.next = p2;
            p1 = p1.next;
            p2 = p2.next;
            p1.next = tmp;
            p1 = p1.next;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode newHead = new ListNode();
        while (head != null) {
            ListNode tmp = newHead.next;
            newHead.next = head;
            head = head.next;
            newHead.next.next = tmp;
        }
        return newHead.next;
    }



    public static void main(String[] args) {
        ListNode head = generateList(new int[] {1,2,3,4,5});
        Solution143 solution143 = new Solution143();
        solution143.reorderList(head);
    }
}
